package HighMethod03;

import java.util.LinkedList;
import java.util.Queue;

public class TestDemo02 {


    public static void PreOrder(int[] arr, int i, int n) {

        if (i < n && arr[i] != -1) {
            System.out.print(arr[i] + " ");
            PreOrder(arr, i * 2 + 1, n);
            PreOrder(arr, i * 2 + 2, n);
        }

    }

    public static void InOrder(int[] arr, int i, int n) {

        if (i < n && arr[i] != -1) {
            InOrder(arr, i * 2 + 1, n);
            System.out.print(arr[i] + " ");
            InOrder(arr, i * 2 + 2, n);
        }

    }

    public static void PastOrder(int[] arr, int i, int n) {

        if (i < n && arr[i] != -1) {
            PastOrder(arr, i * 2 + 1, n);
            PastOrder(arr, i * 2 + 2, n);
            System.out.print(arr[i] + " ");

        }
    }

    //层次遍历
    public static void LevelOrder(int[] arr, int i, int n) {

        Queue qu = new LinkedList();
        qu.offer(i);

        int tmp = -1;
        while (!qu.isEmpty()) {
            System.out.print(arr[(int) qu.poll()] + " ");
            tmp = i * 2 + 1;
            if (tmp < n&&arr[tmp] != -1) {
                qu.offer(tmp);
            }
            tmp = i * 2 + 2;
            if (tmp < n&&arr[tmp] != -1)
                qu.offer(tmp);
            i++;
        }
    }


    /**
     * 给定一个数组，它是仿造完全二叉树存储的，请把它的前中后序遍历写出来（层次遍历）
     *
     * @param args
     */
    public static void main(String[] args) {
        int[] atree = {3, 9, 15, 8, 5, -1, 7, -1, -1, 10, 20};
/**
 *                  3
 *             9          15
 *         8      5    -1      7
 *      -1   -1   10        20
 */
//        PreOrder(atree, 0, atree.length);
//        System.out.println();
//
//        InOrder(atree, 0, atree.length);
//        System.out.println();
//
//        PastOrder(atree, 0, atree.length);
//        System.out.println();
//
//        LevelOrder(atree,0,atree.length);


    }
}
